This invention relates to programmable logic integrated circuits. In particular, the invention relates to a new architecture which provides for greater utility and flexibility of programmable logic devices ("PLDs"), and allows for programmable logic devices of much greater complexity than previously were possible.
The following references are background to this invention: Hartmann et al. U.S. Pat. No. 4,617,479; Hartmann et al. U.S. Pat. No. 4,609,986; Veenstra U.S. Pat. No. 4,677,318; Hartmann et al. U.S. Pat. No. 4,713,792; Birkner et al. U.S. Pat. No. 4,124,899; Cavlan U.S. Pat. No. 4,703,206; Spencer U.S. Pat. No. 3,566,153; J. C. Leininger, "Universal Logic Module", IBM Technical Disclosure Bulletin, Vol. 13, No. 5, October 1970, pp. 1294-95; Ronald R. Munoz and Charles E. Stroud, "Automatic Partitioning of Programmable Logic Devices", VLSI Systems Design Magazine, October 1987, pp. 74-78, and 86; and E. Goetting et al., "A CMOS Electrically-Reprogrammable ASIC with Multi-Level Random Logic Capabilities", 1986 IEEE International Solid State Circuits Conference (Proceedings), pp. 244, 245, 359, and 360. All of these references are hereby incorporated by reference herein.
Several approaches have been used for the architecture of programmable logic integrated circuits. Among these are the "programmable AND, fixed OR" structure (referred to as a PAL) used in the above-mentioned Birkner et al. patent. This architecture has the advantages of higher speed and a simpler structure. However, because it has a fixed number of "product terms" ("P-terms") per OR logic function (eight P-terms is typical of most current PAL products), and because these P-terms cannot be shared by neighboring OR gates, many P-terms are typically wasted. On the other hand, there are many occasions when eight P-terms are not enough to handle the more complex logic functions. Experience has shown that in a broad range of applications, eight P-terms is much more than enough (on average), and yet it is often insufficient. For example, FIG. 2 in the above-mentioned Munoz et al. article is a graph of P-term requirements for a relatively large sample of logic functions (Munoz et al. FIG. 2 is substantially reproduced herein as FIG. 1). Similar studies done by the assignee of the present invention arrive at roughly similar conclusions: namely, a large percentage of logical functions (on the order of 50 to 70 percent) require less than four P-terms. However, a relatively significant "tail" exists where eight P-terms is not enough.
One way to achieve higher P-term utilization is to provide "variable P-term distribution". In essence, this is an to attempt to guess a mixture of P-term requirements such that some OR gates have few P-terms (e.g., four), and some have a relatively large number (e.g., 12 or 16). See, for example, above-mentioned U.S. Pat. No. 4,609,986. This partially solves the problem of P-term utilization, but it significantly increases the complexity of the software support task because each function must be examined and then, depending upon its demand for P-term resources, assigned to a specific macrocell which has the minimum resources needed to fulfill the required demand (this process is called "fitting"). However, even with variable P-term distribution, many P-terms are still wasted.
Another way in which this P-term allocation problem can be solved is suggested in the abovementioned paper by Leininger. With this structure, the P-term array is viewed as an array of programmable NOR or NAND gates whose inputs are programmable. Functions which require more than a single P-term are broken into multi-level NAND (or NOR) functions. Each level of (e.g., NAND) logic takes one P-term. Using this type of array, even quite complex logic functions can be done in a few levels of NAND logic. Again, however, there are some drawbacks. First, it is very likely that most logic functions will take more than a single P-term. This means that most often, two passes through the array will be required, and this causes a slowing down of evaluation of the function. Second, each P-term must feed back into the array input section. Thus, as the number of P-terms grows, so does the number of input lines. Even for arrays of modest complexity, the number of input signal lines (sometimes called "word lines") becomes excessive. For example, the part described in the above-mentioned IEEE ISSCC paper has only eight macrocells but has nearly 100 word lines, while a PAL circuit of similar complexity has only half as many word lines. Each word line adds to the length (and therefore the parasitic capacitance) of all of the P-terms. Greater P-term length leads to slower part operation.
Finally, there are programmable logic arrays ("PLAs") of the type described in the above-mentioned Spencer patent. Most (if not all) functions can be accomplished in one pass through the "AND" array plus one pass through the "OR" array. However, even the simplest functions require these two array delays. Thus, compared to the PAL architecture, there is a speed penalty (for all functions regardless of complexity). This type of PLA circuit is also more complex to execute in silicon because of the need for interface buffering between the AND and the OR array, and because of the inherently more complex programming circuits needed to program the two arrays.
In view of the foregoing, it is an object of this invention to provide an architecture for programmable logic devices which allows for the implementation of PLDs of much greater complexity.
It is another object of the invention to maximize the utilization of word lines and P-terms in PLDs.
It is a further object of the invention to make PLDs of high complexity that can operate at high speed.
It is a further object of the invention to provide a macrocell which is simpler and provides for increased functionality.
It is a further object of the invention to provide a regular, repeatable architecture which will be easy for a user to understand and easy for software tools to support.
It is a further object of the invention to create a modular architecture in which the number of macrocells can be easily increased or decreased, thereby permitting many variations of the same basic design.
It is another object of the invention to provide programmable logic devices which respond correctly to noisy or slowly changing input signals.